This invention relates generally to optical scanners for the measurement and reproduction of objects in three dimensions. More particularly, the invention relates to an apparatus and method for generating three-dimensional shape information through the use of two-dimensional images.
Various methods and devices have been employed to optically scan the three-dimensional shape of objects. However, as discussed below, the conventional methods and apparatus have inherent drawbacks that impose limitations on the approach and on the quality of the resulting data.
Range from Focus
It is well known that using a high speed image processing computer, the sharpness of an image can be measured in real-time at any point in the image where there is a distinguishable feature. There is a direct relationship between focus and range. Thus, in general, if focus is determined in real-time, range can likewise be determined in real-time. In order to determine the range to a multiplicity of points, the sharpness of focus must be determined for each of those points. In order to obtain this information, many images must be captured with different focal distances. If a part of the image is determined to be in focus, then the range to that part of the image can be easily calculated. The focal length must, in effect, be swept from too closexe2x86x92just rightxe2x86x92too far.
The range from focus method has several drawbacks and disadvantages. First, the method requires expensive hardware. The method is also slow because many different focus settings must be used, and at each focus setting, a new image must be captured and analyzed. Furthermore only the range to distinguishable features can be computed.
Time-Of-Flight
Three-dimensional (3D) ranging methods based on the concept of xe2x80x9ctime of flightxe2x80x9d directly measure the range to a point on an object by measuring the time required for a light pulse to travel from a transmitter to the surface and back to a receiver or by the relative phase of modulated received and transmitted signals. The xe2x80x9claser radarxe2x80x9d approaches actually scan with a single spot, and effectively measure the range to each point in the imagexe2x80x94one point at a time. Since the light beam must scan over the full object, this method requires an extensive period of time to complete.
Active Triangulation
Range finding by triangulation is based on the principal that if a base line and the two angles of a triangle are known the lengths of the other sides may be determined. In a basic form of active triangulation, a beam of light is used to form a bright stripe on an object""s surface and a camera displaced a known distance (base line) from the light source views the scene. One angle of the triangle is defined by the angle to the base line of the beam of the light and the other angle is measured via the position of the light strip in the camera (CCD array or lateral effect photodiode).
Active Triangulation Using a CCD Camera
Active Triangulation using a CCD camera generally comprises scanning a plane of light rapidly across a scene or object so that the entire scene is scanned within one frame time. The CCD camera is designed and constructed such that the output values of camera pixels represent the angle at which the scanning line hit the pixels. The geometry of the CCD array provides an additional angle associated with the pixels so the range can be calculated based on these two angles and the length of the base line. The camera pixels are implemented using capacitors which store a given charge before plane light scanning starts and gradually discharge during scanning until the bright line image passes through the pixel. Arithmetic logic is then employed to count the remaining charges on each capacitor and provides angle information at each pixel. This method generally provides high speed and single pixel resolution range image. However, it still requires a scanning plane of light.
Structured Illumination
In structured illumination, a pattern of light, such as an array of dots, strips, or a grid is simultaneously projected onto a scene. However, a major limitation of this method is that each of the stripes in the image must be precisely matched with each of the projected strips. Furthermore, such method cannot achieve single pixel resolution of range image because processing information from a group of pixels is required to determine the location of a structured light element (a dot or a stripe) in the image.
Moirxc3xa9 Contouring
Moirxc3xa9 techniques similarly employ a form of structured light, typically a series of straight lines in a grating pattern, which is projected onto an object in the scene. The projected pattern is then viewed from some other angle through a secondary grating, presenting a view of the first grating line which has been distorted by the contour of the part. To determine the three-dimension contour of the object, moirxc3xa9 techniques based on phase shifting, fringe center mapping, and frequency shifting are employed. The noted shifting and mapping processes do however require extensive software analysis and rigorous hardware manipulation to produce different moire patterns of the same object.
Stereo Vision
A conventional method of measuring a three dimensional (3D) surface profile of objects is stereo vision. A stereo vision system uses at least two cameras to observe a scene similar to human vision. By processing the images from all the cameras, the 3D surface profile of objects in the scene can be computed via triangulation of common features. This requires finding a common feature that is visible in more than one image, which requires extensive computation and artificial intelligence to avoid the confusion of features with one another. As with the range from focus approach, range can only be determined at points in the object where there is a discernable feature, and because this information must be extracted from a group of pixels, it cannot be pixel accurate at every point in a feature. Structured lighting is often applied to the object to produce easily recognizable features where they would otherwise be absent.
Projected Patterns
The problem of ambiguity (i.e., confusion of lines or bands with one another) that typically arises with structured illumination can be alleviated though the careful design of the projected pattern. One xe2x80x9cprojected patternxe2x80x9d approach involves employing a multitude of patterns that complement one another and coding each specific stripe by way of its appearance under all of the patterns in the set. This does however require the capturing of many images to secure all the patterns.
To achieve single or sub-pixel accuracy in the triangulation or stereo correspondence, uniform stripes in the structured light pattern are replaced with continuously or discretely varying functions in the direction to be triangulated. These functions are applied to the light""s intensity, color, or wavelength. Indeed, in some instances, the entire structured light pattern can be one single functional field. Taking the approach to this extreme avoids the problem of multiple patterns, but it seriously compromises the accuracy of the measurement, since the discernable range of intensity, color, or wavelength is being mapped across the entire field of image instead of just a narrow strip.
It is therefore an object of the present invention to provide a photogrammetric alignment method and apparatus that improves, by means of a more effective projection pattern, the quality, performance, and feasibility of all three-dimensional (3D) scanner configurations in which structured illumination is or potentially could be employed.
In accordance with the above objects and those that will be mentioned and will become apparent below, the photogrammetric alignment method and apparatus in accordance with this invention comprises at least one energy radiation source to illuminate the object in the scene and at least one camera or other type of two-dimensional (2D) image sensor array to obtain at least one image of the object to be scanned. The projection is accomplished by means that produce a projection pattern, such as a conventional projector. In a preferred embodiment, the projector includes a photographic or infrared filtering slide to facilitate the projection of the pattern.
According to the invention, a unique multi-color (i.e., tricolor) projection pattern is generated and employed, which provides both sub-pixel level accuracy in the determination of an illuminated object""s two-dimensional position at any point in the light field, and a unique local identification, within the global context of the entire illumination field, of the transverse position of any illuminated area on the object, without requiring a plurality of projections.
In one embodiment of the invention, the projected pattern is used in conjunction with conventional computer vision techniques. In the noted embodiment, at least one region of the object being scanned is illuminated with space modulated (as opposed to time) radiant energy. At least one camera is employed to acquire digital images of the illuminated portion of the object from at least one known position and orientation. Matching features in the photographs are found via digital image processing of the images. These matching features are then processed through conventional triangulation computer vision algorythms to determine the 3D position at each point.
The unique pattern of the invention provides for very precise position measurements by using functions in both the transverse (horizontal) and perpendicular (vertical) direction. In the transverse direction, the pattern comprises a series of vertical bands. The intensity (radiance) of the colored light also varies functionally within each band.
In the perpendicular direction, the hue (expressable as a function of the dominant wavelength) of the illuminating light varies functionally along the band. The hue can also repeat itself more than once along the extent of the projected field to improve the discernable precision of position from hue measurements. In practice, hues are generated by adjusting the relative levels of the tri-color source channels.
The pattern also provides for the exact identification of any local area within the global context of the entire illumination field through a technique, referred to herein as xe2x80x9chue-shift tagging.xe2x80x9d In this technique, successive bands in the pattern are discerned by a quantified shift in hue at their boundary. Each shift is then measured in terms of a whole number multiple of the smallest allowed shift; the multiple being the hue-shift at each band.
According to the invention, the sequence of hue-shifts across the entire pattern is designed such that a locally discernable xe2x80x9ctagxe2x80x9d, consisting of one to five successive hue-shift values, preferably occurs only once in the entire extent of the pattern. A local analysis of an image under the pattern can thus identify each band of the projected pattern globally.
The xe2x80x9chue-shift taggingxe2x80x9d technique makes it possible for the first time to precisely locate matching features for computer vision 3D from widely disparate views. It is the first approach to incorporate functional variation in two separate dimensions, which frees the computer vision process from the constraint that epipolar lines must remain horizontal to the pattern. This greatly reduces the number and proximity of images that need to be acquired.